package com.matrix.java.chap_07;

import java.util.Arrays;

public class Ex7_16 {
    public static void main(String[] args) {
        int[] arr = new int[100000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random()*10000);
        }
        long start = System.currentTimeMillis();
        System.out.println(linearSearch(arr, 44));
        long end = System.currentTimeMillis();

        System.out.println(start-end);

        long start1 = System.currentTimeMillis();
        Arrays.sort(arr);
        System.out.println(binarySearch(arr, 44));
        long end1 = System.currentTimeMillis();

        System.out.println(start1-end1);
    }
    private static int linearSearch(int[] list, int key) {
        for (int i = 0; i < list.length; i++) {
            if (key==list[i]){
                return i;
            }
        }
        return -1;
    }
    public static int binarySearch(int[] list, int key){
        int low = 0;
        int high = list.length - 1;
        while (high>=low){
            int mid = (low + high) / 2;
            if (key<list[mid]){
                high = mid-1;
            }else if (key==list[mid]){
                return mid;
            }else {
                low = mid +1;
            }
        }
        return -low-1;
    }
}
